public class Sort {
//    public static void insertSort(int[] array){
//        for (int i = 1; i < array.length; i++) {
//            int j=i-1;
//            int temp=array[i];
//            for (; j > 0; j--) {
//                if(array[j]>temp){
//                    array[j+1]=array[j];
//                }else{
//                    break;
//                }
//            }
//            array[j+1]=temp;
//        }
//    }
//    public static void insertSort(int[] array){
//        for(int i=1;i<array.length;i++){
//            int j=i-1;
//            int temp=array[i];//这里的循环逻辑
//            //j的下标是不会超过i的,temp会和i后面所有的值进行比较,i后面的值又是由j下标来控制,
//            //所以j的这个循环就是在打擂台j下标的值依次与temp比较,如果满足判断条件则执行语句.
//            //这里记住,i前面的值是有序的
//            for (; j > 0; j--) {
//                if(array[j]>temp){
//                    array[j+1]=array[j];
//                }else {
//                    break;
//                }
//            }
//            array[j+1]=temp;//这行代码意思是如果刚进入里层循环,就break了,那么j就没有减减,那么temp位置不动
//            //还有就是j减减了,也就是前面进行了
//            //交换,这里说交换,其实就是让前面一个数据往前挪动,这时j的位置,就是在原来没挪动元素的位置,这时你要把数据插入到这个地方.
//        }
//    }
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int temp=array[i];
            int j=i-1;
            for(;j>0;j--){
                if(array[j]>temp){
                    array[j+1]=array[j];
                }else{
                    break;
                }
                array[j+1]=temp;
            }
        }
    }
    public static void shell(int[] array,int gap){
        for (int i = gap; i < array.length; i++) {
            int temp=array[i];
            int j=i-gap;
            for(;j>0;j--){
                if(array[j]>temp){
                    array[j+gap]=array[j];
                }else{
                    break;
                }
                array[j+gap]=temp;
            }
        }
    }
    public static void shellSort(int[] array){
        int gap=array.length;
        while(gap>1){
            gap=gap/3+1;
            shell(array,gap);
        }
    }



    //先创建一个大根堆
    public void creatBigHeap(int[] array){
        int child=array.length-1;
        for (int parent=(child-1) /2; parent >=0 ; parent--) {
            shiftDown(parent,array,child);
        }
    }
    public void swap(int x,int y,int[] array){
        int temp=array[x];
        array[y]=array[x];
        array[x]=array[y];
    }
    private void shiftDown(int parent,int[]array ,int end){
        int child=(parent-1)/2;
        while(child<end){
            if(child+1<end&&array[child]<array[child+1]){
                child++;
            }
            if(array[parent]<array[child]){
                swap(parent,child,array);
                parent=child;
                child=parent*2+1;
            }else {
                break;
            }
        }
    }
    public  void heapSort(int[] array){
        creatBigHeap(array);
        int child=array.length-1;
        while (child>=0){
            swap(0,child,array);
            shiftDown(0,array,child);
            child--;
        }
    }
    public void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex=i;
            for (int j = 1; j < array.length; j++) {
                if(array[j]<array[i]){
                    minIndex=i;
                }
            }
            swap(i,minIndex,array);
        }
    }
}
